|
In the theory of Optimal binary search trees, the interleave lower bound is a lower bound on the number of operations required by a binary search tree (BST) to execute a given sequence of accesses. Several variants of this lower bound have been proved. This article is based on one of the variants. == Definitions == The bound is based on a ''perfect BST'', P, which contains the keys 1,2,...,''n''. The structure of ''P'' is fixed. For example, for ''n''=7, ''P'' can be represented by the following parenthesis structure: ::) 4 (() 6 ())] For each node ''y'' in P, define: * ''Left(y)'' = ''y'' itself and its left subtree; * ''Right(y)'' = the right subtree of ''y''. There is a sequence of accesses to elements of the tree: ''X'' = (''x1'', ''x2'', ..., ''xm''). For each access ''x'' and node ''y'', define the label of ''x'' for ''y'' as: * "''L''" - if ''x'' is in ''Left(y)''; * "''R''" - if ''x'' is in ''Right(y)''; * null - otherwise. The label of ''y'' is the concatenation of the labels from all the accesses. For example, if the sequence of accesses is: 7,6,3, then the label of the root (4) is: "RRL", the label of 6 is: "RL", and the label of 2 is: "R". For every node ''y'', the ''amount of interleaving through y'' is the number of alternations between L and R in the label of ''y''. In the above example, the interleaving through 4 and 6 is 1 and the interleaving through all other nodes is 0. The ''interleave bound'', , is the sum of the interleaving through all the nodes of the tree. The interleave bound of the above sequence is 2. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Interleave lower bound」の詳細全文を読む スポンサード リンク
|